1. Field of the Invention
The present invention relates to a tile binning method and system using a half plane edge function, and more particularly, to a method and system in which a scene for performing three-dimensional rendering of a triangle is divided into a plurality of tiles and a tile including an entirety or a part of the triangle is identified to perform the rendering with respect to only the tile including the entirety or the part of the triangle, from the divided tiles.
2. Description of the Related Art
Currently, as the performance capability of portable terminals improves, the instances of providing information using three-dimensional graphics are increasing. Though three-dimensional graphics could be used in only a computer terminal in the past, as the performance capability of portable terminals such as a mobile phone, a personal data assistant (PDA), or a navigation device, improves, three-dimensional graphics may be used in these portable terminals. When using three-dimensional graphics, even a two-dimensional display device may more realistically express a three-dimensional model.
However, when a three-dimensional model is expressed by using three-dimensional graphics, since the display device shows a two-dimensional scene to a user, a process of converting a three-dimensional model into the two-dimensional scene viewed by the user, is required. The process of converting the three-dimensional model into a two-dimensional scene by generating a three-dimensional model converted into two-dimensional coordinates and displayed in the form of a vector, as a pixel-based two-dimensional scene, is called rasterization. In rasterization, the two-dimensional scene based on a triangle that is a basic unit of the three-dimensional model is generated.
According to a conventional method, each of triangles that have to be processed in the rasterization process is processed with respect to an entire scene, and a frame buffer (a color buffer+Z buffer) having the same size of scene resolution is required. In this case, since it is difficult to embed the frame buffer in a chip, due to the size of the frame buffer, access is performed via random external memory. Since the external memory access consumes approximately ten times the amount of power of an on-chip memory access, it becomes an important to reduce a frequency of external memory access in a mobile environment. Accordingly, a tile-based three-dimensional rendering method is developed to solve the problem of the conventional method.
FIG. 1 is a diagram illustrating a related art tile-based three-dimensional rendering method. Referring to FIG. 1, tiles 120 include an entirety or a part of a triangle 110, and other tiles do not include any part of the triangle 110. In this case, rendering with respect to one tile is performed by using a frame memory having a size of one tile resolution embedded in a chip. When the rendering with respect to one tile is completed, it may be transmitted to a tile position of an external frame buffer at one time in a burst mode. According to the tile-based rendering method, since there is not frequent external frame buffer memory access and one effective external burst memory access performed, it is very advantageous from a low power driving perspective.
To perform the tile-based three-dimensional rendering method, the tiles 120 including the entirety or the part of the triangle 110 must be identified, which is called tile binning. However, tile binning is not required in existing rendering methods and causes heavy loads in the tile-based three-dimensional rendering method. It is also very difficult to precisely identify the entirety or the part of the triangle 110. Accordingly, a method capable of precisely identifying the tiles 120 including the entirety or the part of the triangle 110 is required.
FIG. 2 is a diagram illustrating a related art tile binning method using division. The conventional tile-binning method using division is designed to quickly identify tiles including an entirety or a part of a triangle 210. Referring to FIG. 2, a minimal square 220 including the triangle 210 is acquired as shown in grid 201. When a size of the minimal square 220 is greater than a predetermined threshold, as shown in grid 202, the triangle 210 is divided into four triangles, by connecting middle points of three edges of the triangle 210 and minimal squares including each of the divided triangles are acquired. The above process is repeated until the size of each of the minimal squares is smaller than the threshold. When the size of the minimal square is smaller than the threshold, tiles including the squares are identified as tiles including the entirety or the part of the triangle 210.
However, according to the above method, as shown in 202, tiles 230 identified as the tiles including the entirety or the part of the triangle 210 that actually do not include any part of the triangle 210 may exist. Therefore, completely precise processing cannot be expected. Also, since a number of triangles is increased by a factor of four for each step, when a size of a triangle is great and there are many steps, the number of triangles is increased according to a geometric progression 4n, thereby decreasing operation speed and becoming very slow. A process of rearranging newly generated fixed points in the form of a triangle may be an additional overhead in an embodiment, unlike the simplicity of the algorithm itself.
Accordingly, when there is a method capable of precisely identifying tiles including an entirety or a part of a triangle and expecting a certain performance regardless of a form or a size of the triangle, a tile binning method may be more efficiently performed.